/**
 * 数组中的最长连续子序列
 *
 * 描述
 * 给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）
 *
 * 数据范围：1≤n≤10^5，数组中的值满足1≤val≤10^8
 *
 * 要求：
 * 空间复杂度 O(n)
 * 时间复杂度 O(nlogn)
 */

import java.util.HashSet;
import java.util.Set;

/**
 * 这一题利用 set 将所有的数存储起来,
 * 后面在遍历数组中的每一个数, 看看是否可以连续起来,
 * 这里一定是要这个数是起点才开始循环判断
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(n)
 */


public class Main {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int MLS (int[] arr) {
        // write code here

        int n = arr.length;

        // 存储 每个数
        Set<Integer> hash = new HashSet<>();

        for (int i = 0; i < n; i++) {
            hash.add(arr[i]);
        }

        // 最大长度
        int maxLen = 0;

        for (int x : arr) {

            // 确定是否是起点
            if (!hash.contains(x - 1)) {

                // 当前长度
                int res = 1;

                // 当前数字
                int currentX = x;

                // 判断是否有下一个数
                while (hash.contains(currentX + 1)) {
                    res++;
                    currentX++;
                }

                // 长度更新
                maxLen = Math.max(maxLen, res);
            }
        }

        // 返回结果
        return maxLen;
    }
}